It is often times desirable in communications networks to attempt to equalize the distribution of traffic across network nodes so as to alleviate network congestion and in order to promote the utilization of network resources as cost-effectively as possible. Typically, one will be met with the task of forwarding or distributing network traffic from a source and to a destination across multiple links, paths or path segments that are equivalent or which may be deemed to be equivalent to one another. For instance, such equivalent multiple links, paths or path segments may be characterized by having the same or a comparable cost of transmission to a given destination. As used in this specification, an equivalent path will signify a link, path or path segment that is considered to have one or more identical or similar transmission attributes to an alternative link, path or path segment. Likewise, an equivalent path as used herein will denote a link, path or path segment that will produce identical or similar traffic consequences if deployed in substitution for an alternative link, path or path segment.
In the particular case of networks that employ connectionless network protocols, for example in Internet Protocol (IP) networks, circumstances will routinely arise where traffic must be forwarded to a destination through a network node which possesses equivalent paths known as equal cost multiple paths (ECMPs). One factor which promotes the availability of ECMPs in these networks is that network links, paths or path segments are many times assigned the same default cost by existing forwarding protocols such as Open Shortest Path First (OSPF), Border Gateway Protocol (BGP) or Intermediate System—Intermediate System (ISIS). In forwarding traffic at and from each node within connectionless protocol networks, it therefore becomes a requirement to select among any number of available ECMPs. Such selection must be undertaken while attempting to meet the goals previously mentioned of minimizing network congestion and of promoting an effective utilization of network resources.
To maintain packet ordering in connectionless network protocols, it is desirable for packets belonging to the same flow to be forwarded over the same source-to-destination path. In other words, packets having the same source address and destination address are typically forwarded over the same path so as to preserve packet sequencing. To this end, a router or other network node will employ the source and destination addresses of a packet in order to select the next path segment where there exist a number of available ECMP segments towards the relevant destination of the packet. Typically, a randomized selection function is provisioned to operate on the source and destination addresses of each packet for the purpose of generating a path pointer that is associated with an available ECMP. The randomized selection function in question is intended to produce a distribution of packed traffic mere or less evenly among multiple ECMP segments at each network node.
An example of a randomized function used for path selection is a hashing function or algorithm, as is well known to those skilled in this art. Since such functions or algorithms will make use of the source and destination addresses of each packet in order to achieve path selection, packets associated with the same traffic flow will be forwarded along the same downstream path segment at a given node of the network, thereby preserving packet sequencing. Where packets are associated with different traffic flows, the random nature of hashing functions or algorithms that are employed for path selection will generally promote the desired result of distributing traffic of different flows equally among all available ECMP segments at a given network node.
One phenomenon, known to those in this art as ECMP polarization, occurs at the network level with the use of path selection routines such as the hashing functions or algorithms described above. In theory, the random nature of hashing functions or algorithms, together with the relative uniqueness of each source and destination address pair for a given traffic flow, should promote the tendency to distribute network traffic evenly among all ECMP segments at each network node along a traffic path. In practice, however, a subsequent node in a network could very well employ the identical hashing function or algorithm as its predecessor. For instance, this may occur where network equipment at two contiguous nodes in a network are provided by the same vendor. If an identical hashing function or algorithm is so employed, the use of a given source and destination address pair with the same hashing function or algorithm will result in the selection of an identical path pointer in the subsequent node as was the case with its predecessor. For instance, a first node may result in the selection of a particular path pointer based upon a specific hashing function or algorithm and address pair. Such a path pointer may be associated with the third ECMP segment among those that are available for selection by the first node. A second node downstream from the said first node may employ the same hashing function or algorithm as the first node. For the same traffic flow as identified by address pair, then, this second node will select the identical path pointer as the first node. Once again, this could be associated with the third ECMP segment of those which are available for selection by the second node. As a result, network traffic in this example would be forwarded in the same manner on two adjacent nodes of the network. Namely, each of the nodes of this example will generate the same path pointer that will be associated with the respective third ECMP path segment available to the nodes. This will produce a polarized traffic distribution for the two nodes in question. In the extreme, all nodes along a path could potentially exhibit this same behavior, resulting in polarization across the entire source-to-destination path.
It has been known to attempt to design network configurations with different hashing functions or algorithm at the nodes thereof as a means of addressing the phenomenon of network polarization. However, this known solution would have the disadvantage that all affected nodes of the network would require different software or hardware to be loaded therewith. This would raise obvious inconvenience for equipment vendors. Another attempted solution may have involved the injection of a mathematical constant or variable within existing hashing functions or algorithms to render them mathematically unique from one another across various nodes within a network. However, those skilled in this art will understand that such an approach would not necessarily resolve the occurrence of traffic polarization, since all such existing hashing algorithms will utilize a source address and a destination address as its expected mathematical inputs, and such known functions or algorithms may very well produce a given repeatable pattern of path selection for the same address pairs notwithstanding the injection of a unique mathematical constant or variable as aforesaid.
It is therefore an object of the present invention to attempt to reduce or alleviate the problem of polarized network traffic distribution where one or more nodes within a communications network possess multiple equivalent path segments for forwarding network traffic.